package BinaryTree;

import BinaryTree.CompleteBinaryTree.CompleteBinaryTree;

/**
 * 满二叉树：每一层的节点都是满的
 *
 * @author Liaorun
 */
public class FullBinaryTree {

    public static class Info {
        /**
         * 树的高度
         */
        public int height;
        /**
         * 树的节点个数
         */
        public int nodes;

        public Info(int height, int nodes) {
            this.height = height;
            this.nodes = nodes;
        }
    }

    public static boolean isFull(CompleteBinaryTree.Node head) {
        if (head == null) {
            return true;
        }

        Info data = process(head);

        // 树的节点个数 = 树的高度 * 2 - 1
        // 就是满二叉树
        return data.nodes == (1 << data.height - 1);
    }


    public static Info process(CompleteBinaryTree.Node x) {
        if (x == null) {
            return new Info(0, 0);
        }

        Info leftData = process(x.left);
        Info rightData = process(x.right);

        // 当前树的高度 = Math.max(左子树的高,右子树的高） + 1
        int height = Math.max(leftData.height, rightData.height) + 1;
        // 节点个数 = 左子树节点个数 + 右子树节点个数 + 1
        int nodes = leftData.nodes + rightData.nodes + 1;

        return new Info(height, nodes);
    }
}
